#include <iostream>
#include <string>
#include <math.h>
int edit_distance(std::string s1, std::string s2);

int edit_distance(std::string s1, std::string s2)
{   
    const char *p1 = s1.data();
    const char *p2 = s2.data();

    int dp[s1.length() + 1][s2.length() + 1];
    for (int i = 0; i <= s1.length(); i++)
        dp[i][0] = i;
    
    for (int j = 0; j <= s2.length(); j++)
        dp[0][j] = j;
    
    for (int i = 1; i <= s1.length(); i++)
    {
        for (int j = 1; j <= s2.length(); j++)
        {
            if (p1[i-1] == p2[j-1])
                dp[i][j] = 1 + fmin(dp[i][j-1], fmin(dp[i-1][j], dp[i-1][j-1] - 1));
            else
                dp[i][j] = 1 + fmin(dp[i][j-1], fmin(dp[i-1][j], dp[i-1][j-1]));
        }
    }
    return dp[s1.length()][s2.length()];
}

int main()
{
    using namespace std;
    cout << edit_distance("horse", "ros") << endl;
    cout << edit_distance("intention", "execution") << endl;
    return 0;
}